import collections


class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def boundaryOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = collections.deque([root])
        out_val = [root.val]
        node = root
        while node.left or node.right:
            if node.left:
                node = node.left
                out_val.append(node.val)
            else:
                if node != root:
                    node = node.right
                    out_val.append(node.val)
                else:
                    break
        left_last_node = node
        node = root
        right_val = []
        while node.right or node.left:
            if node.right:
                node = node.right
                right_val.append(node.val)
            else:
                if node != root:
                    node = node.left
                    right_val.append(node.val)
                else:
                    break
        right_val.reverse()
        right_last_node = node
        while stack:
            node = stack[-1]
            if node.left:
                stack.append(node.left)
            else:
                node = stack.pop()
                if not node.right:
                    if node != left_last_node and node != right_last_node:
                        out_val.append(node.val)
                while stack and not node.right:
                    node = stack.pop()
                if node.right:
                    stack.append(node.right)
        out_val += right_val
        return out_val





